package main

import "fmt"

var dirs = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

func getMaximumGold(grid [][]int) int {
	var max = 0
	m, n := len(grid), len(grid[0])

	var dfs func(x, y, sum int)
	dfs = func(x, y, sum int) {
		temp := grid[x][y]
		sum += temp
		if sum > max {
			max = sum
		}
		grid[x][y] = 0
		m, n := len(grid), len(grid[0])
		for _, v := range dirs {
			nx, ny := x+v[0], y+v[1]
			if nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] == 0 {
				continue
			}
			dfs(nx, ny, sum)
		}
		grid[x][y] = temp
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] != 0 {
				dfs(i, j, 0)
			}
		}
	}
	return max
}

func main() {
	fmt.Println(getMaximumGold([][]int{{0, 6, 0}, {5, 8, 7}, {0, 9, 0}}))
	fmt.Println(getMaximumGold([][]int{{1, 0, 7}, {2, 0, 6}, {3, 4, 5}, {0, 3, 0}, {9, 0, 20}}))

}
